﻿#include<iostream>

#define MAXSIZE 20

using namespace std;

typedef struct {
	int r[MAXSIZE + 1];//r[0]闲置做哨兵
	int length;
}SqList;

struct ListNode {
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

//稳定排序算法 插入(折半插入) 冒泡 归并 基数 选择
//时间复杂度O(N^2):插入(折半插入) 冒泡 选择
//时间复杂度O(N^logN):快速 堆 归并
//空间复杂度O(1):插入(折半插入) 冒泡 选择  希尔 堆
//空间复杂度O(N):归并
//空间复杂度O(logN):快速

//一、插入排序

//①直接插入法(最好情况下是O(N))//带哨兵
//适用于链式 适用于初始记录基本有序的情况
void InsertSort(SqList& L) {
	if (L.length <= 1)
		return;
	int j;
	for (int i = 2; i <= L.length; ++i) {
		if (L.r[i] < L.r[i - 1]) {
			L.r[0] = L.r[i];
			for (j = i - 1; L.r[0] < L.r[j]; --j)
				L.r[j + 1] = L.r[j];
			L.r[j + 1] = L.r[0];
		}
	}
}

//②折半插入(带哨兵)
//由于是折半 只使用于顺序结构 不适用于链式结构
//适用于初始无序 并且n较大的情况
void BInsertSort(SqList& L) {
	if (L.length <= 1)
		return;
	int low, high, mid;
	for (int i = 2; i <= L.length; ++i) {
		L.r[0] = L.r[i];
		low = 1;
		high = i - 1;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (L.r[mid] <= L.r[0])
				low = mid + 1;
			else
				high = mid - 1;
		}
		for (int j = i - 1; j >= high + 1; --j)
			L.r[j + 1] = L.r[j];
		L.r[high + 1] = L.r[0];
	}
}

//③希尔排序 最坏O(N^2) 但平均复杂度无法计算 通常认为O(N^1.3)
//先将数组分为若干的子表 然后缩小增量d(d<<=1) 对每一个子表进行直接插入排序
void ShellSort(SqList& L, int d) {
	int j;
	while (d >= 1) {
		for (int i = d + 1; i <= L.length; ++i) {
			if (L.r[i] < L.r[i - d]) {
				L.r[0] = L.r[i];
				for (j = i - d; j > 0 && L.r[j] > L.r[0]; j -= d)
					L.r[j + d] = L.r[j];
				L.r[j + d] = L.r[0];
			}
		}
		d -= 2;
	}
}

//二、交换排序

//①冒泡排序 不如直接插入排序 可用于链式结构
//不适用数据量大且无序
void BubbleSort(SqList& L) {
	int m = L.length - 1;
	int flag = 1;
	while (m > 0 && flag) {
		flag = 0;
		for (int j = 1; j <= m; ++j) {
			if (L.r[j] > L.r[j + 1]) {
				swap(L.r[j], L.r[j + 1]);
				flag = 1;
			}
		}
		--m;
	}
}

//②快速排序  时间最好O(NlogN) 最坏O(N^2) 空间最好O(logN) 最坏O(N)
//适用于顺序结构 不适用链表(因为链表不好确定子表的上下界)
//适用于无序 n较大的情况 排序不稳定
//划分越均匀 效率越高
//优化方案 ①选取头尾中间元素 将中间元素置为枢轴②随机选取枢轴元素
int Partition(SqList& L, int low, int high) {
	int pivot = L.r[low];
	while (low < high) {
		while (low < high && L.r[high] >= pivot)
			--high;
		L.r[low] = L.r[high];
		while (low < high && L.r[low] <= pivot)
			++low;
		L.r[high] = L.r[low];
	}
	L.r[low] = pivot;
	return low;
}

void QuickSort(SqList& L, int low, int high) {
	if (low < high) {
		int pivot = Partition(L, low, high);
		QuickSort(L, low, pivot - 1);
		QuickSort(L, pivot + 1, high);
	}
}

//三、选择排序

//①简单选择排序(可用于链式)
void SelectSort(SqList& L) {
	int k;
	for (int i = 1; i < L.length; ++i) {
		k = i;
		for (int j = i + 1; j <= L.length; ++j) {
			if (L.r[j] < L.r[k])
				k = j;
		}
		if (k != i)
			swap(L.r[i], L.r[k]);
	}
}
//②树形选择排序(锦标赛排序)(待实现)
//③堆排序 (顺序存储的二叉树形式)
//大根堆(根节点的值大于等于左节点或右节点)
//小根堆(根节点的值小于等于左节点或右节点)

//以大根堆为例 将初始序列建立为大根堆 建堆的时间复杂度为O(N)
void HeapAdjust(SqList& L, int s, int m);
void CreatHeapL(SqList& L) {
	int n = L.length;
	//1-n/2为原来的非叶子节点
	for (int i = n / 2; i >= 1; --i)
		HeapAdjust(L, i, n);
}
//调整以r[s]为根的大根堆
void HeapAdjust(SqList& L, int s, int m) {
	L.r[0] = L.r[s];//暂存子树的根节点
	for (int i = 2 * s; i <= m; i *= 2) {//沿着值更大的子节点向下筛选
		if (i < m && L.r[i] < L.r[i + 1])
			++i;
		if (L.r[0] >= L.r[i])
			break;
		else
		{
			L.r[s] = L.r[i];
			s = i;
		}
	}
	L.r[s] = L.r[0];
}
void HeapSort(SqList& L) {
	CreatHeapL(L);//O(N)
	for (int i = L.length; i > 1; --i) {
		swap(L.r[i], L.r[1]); //O(NlogN)
		HeapAdjust(L, 1, i - 1);
	}
}
//堆的插入与删除(待实现)

//归并排序
// 辅助数组，用于归并操作
int* mergeArray = new int[11];

// Merge函数实现将两个有序子数组合并为一个有序数组
void Merge(SqList& L, int low, int mid, int high) {
	// 将待合并的子数组元素复制到辅助数组mergeArray中
	for (int k = low; k <= high; ++k)
		mergeArray[k] = L.r[k];
	int i = low, j = mid + 1, k = low;
	// 双指针比较并合并子数组元素
	while (i <= mid && j <= high) {
		mergeArray[k++] = L.r[i] <= L.r[j] ? L.r[i++] : L.r[j++];
	}
	// 处理剩余元素（如果左边子数组还有剩余）
	while (i <= mid)
		mergeArray[k++] = L.r[i++];
	// 处理剩余元素（如果右边子数组还有剩余）
	while (j <= high)
		mergeArray[k++] = L.r[j++];
	// 将合并好的有序元素复制回原顺序表L
	for (int k = low; k <= high; ++k)
		L.r[k] = mergeArray[k];
}
void MergeSort(SqList& L, int low, int high) {
	if (low < high)
	{
		int mid = (low + high) / 2;
		MergeSort(L, low, mid);
		MergeSort(L, mid + 1, high);
		Merge(L, low, mid, high);
	}
}

void PrintArr(const SqList& L) {
	for (int i = 1; i <= L.length; ++i)
		cout << L.r[i] << " ";
	cout << endl;
}

//int main() {
//	SqList L;
//	L.r[0] = INT_MAX;
//	L.r[1] = 49; L.r[2] = 38; L.r[3] = 65; L.r[4] = 97;
//	L.r[5] = 76; L.r[6] = 13; L.r[7] = 27; L.r[8] = 49;
//	L.r[9] = 55; L.r[10] = 4;
//	L.length = 10;
//	//BInsertSort(L);
//	//ShellSort(L, 5);
//	//BubbleSort(L);
//	//QuickSort(L, 1, L.length);
//	//SelectSort(L);
//	//HeapSort(L);
//	MergeSort(L, 1, L.length);
//	PrintArr(L);
//}